package _03_ArrayUse;
/**
 * 当数据过大的时候,想要查找某个数据,并不是一件容易的事,尤其是我们要找的数据可能在最后几条,如果依次比较数据,效率太低
 * 
 * 1.必须建立在已经排序的基础之上
 * 2.没有重复数据
 *
 * 算法实现 :
 * 1.确定数据的开始位置和结束位置
 * 2.确定数据的中间位置,判断中间位置元素是否是目标数据,如果是,就直接返回中间数据对应的下标
 * 3.如果不是,分为两种
 *		1.目标数据大于中间数据
 *		起始值 = 中间值 + 1 , 结束值不变
 *		2.目标数据小于中间数据
 *		结束值 = 中间值 - 1 , 起始值不变
 * 4.终止条件 : 当起始值大于结束值的时候,说明没有这个目标数据
 * @author lenovo
 * @Date 2020年7月1日
 * @Time 下午10:10:17
 */
public class Array_08 {

	public static void main(String[] args) {
//		int[] arr = { 1, 3, 4, 5, 6, 7, 9, 15, 17, 19, 38, 41, 52, 63, 73, 78 };

		int[] arr = new int[21111111];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = i;
		}
		int num = 20011112;
		long startTime = System.currentTimeMillis();
		int index = search(arr, num);
		System.out.println(num + " 在arr数组的第 : " + index + " 位上,执行了 " + count_1 + " 次");
		long endTime = System.currentTimeMillis();
		System.out.println("传统查找使用 : " + (endTime - startTime) + " 毫秒");

		startTime = System.currentTimeMillis();
		index = binarySearch(arr, num);
		System.out.println(num + " 在arr数组的第 : " + index + " 位上,执行了 " + count_2 + " 次");
		endTime = System.currentTimeMillis();
		System.out.println("二分法查找使用 : " + (endTime - startTime) + " 毫秒");
	}

	// 传统查询次数
	static int count_1 = 0;
	// 二分法查询次数
	static int count_2 = 0;

	/**
	 * 传统写法
	 * 
	 * @param arr
	 * @param num
	 * @return
	 */
	public static int search(int[] arr, int num) {
		for (int i = 0; i < arr.length; i++) {
			count_1++;
			if (arr[i] == num) {
				return i;
			}
		}
		// 能到这里说明没有找到,返回 -1
		return -1;
	}

	/**
	 * 二分法查询
	 * 
	 * @param arr
	 * @param num
	 * @return
	 */
	public static int binarySearch(int[] arr, int num) {
		if (arr == null || arr.length == 0) {
			return -1;
		}
		// 1 确定数据的开始位置和结束位置
		int startPos = 0;
		int endPos = arr.length - 1;
		// 2 确定数据的中间位置,判断中间位置元素是否是目标数据,如果是,就直接返回中间数据对应的下标
		int m = (startPos + endPos) / 2;
		// 终止条件 : 当起始值大于结束值的时候,说明没有这个目标数据
		while (startPos <= endPos) {
			count_2++;
			if (num == arr[m]) {
				return m;
			}
			// 3 如果不是,分为两种
			// 1 目标数据大于中间数据
			// 起始值 = 中间值 + 1 , 结束值不变
			if (num > arr[m]) {
				startPos = m + 1;
			}
			// 2 目标数据小于中间数据
			// 结束值 = 中间值 - 1 , 起始值不变
			if (num < arr[m]) {
				endPos = m - 1;
			}
			m = (startPos + endPos) / 2;
		}

		// 能到这里 说明没有找到,直接返回-1
		return -1;
	}
}
